So, guten Morgen. Heute haben wir noch einen kleinen Nachtrag mit dem Anfangen, nämlich zu dem Kapitel über Bilder.

Hatt ich beim letzten Mal ein paar Folien noch übrig zum Thema Kompression, das möchte ich gerne heute behandeln.

Und dann gehen wir ins nächste Kapitel, das sich beschäftigen wird mit Werkzeugen für digitale Editionen.

Und dann Schritt um Schritt geht es mehr und mehr an inhaltliche Erschließung.

Deswegen haben wir uns entschlossen, aus dem Kapitel 10 einen Teil vorzuziehen, wo es um Textanalyse geht.

Und den zweiten Teil, der eigentlich der erste gewesen wäre, dann in der nächsten Stunde zu behandeln.

Da geht es nochmal um Werkzeuge auf XML-Ebene, insbesondere die Frage, wenn ich jetzt eine große XML-Datei habe,

wie kann ich denn da Anfragen stellen gezielt? Und wenn man Anfragesprachen hat, dann ist natürlich die nächste Frage,

kann ich nicht auch einen solchen XML-Inhalt in einer Datenbank abspeichern?

Und dann diese Abfragesprache auch gleich als Abfragesprache für die Datenbank benutzen.

Die Antwort heißt ja und es wird dann das nächste Mal dran kommen.

Wir beginnen jetzt mit Kompressionsverfahren.

Ursprünglich hat man das Kompressionsthema im Zusammenhang mit der Kompression von Textdateien gestellt.

Und da gibt es insbesondere von einem Autor, nämlich Herrn Witten, einige Bücher zu dem Thema.

Eines hat den Titel Managing Gigabytes und das ist vor gut zehn Jahren veröffentlicht worden.

Da war in der Tat größere Textkorporate mit einem Umfang von 1 Gigabyte schon etwas ganz Gewaltiges.

Und nicht nur zum Abspeichern, sondern auch zum Verwalten.

Man hat sich dann mit der Frage beschäftigt, wie kann ich denn solche großen Bestände an Daten effizient komprimieren und dekomprimieren?

Und das Modell, das da entwickelt worden ist, lässt sich natürlich auch auf alle anderen Daten verallgemeinern.

Und man geht etwa so vor. Man hat einen Kodierer und einen Dekodierer.

Beide arbeiten mit sogenannten Modellen. Das sind stochastische Ansätze, in denen eine Vorhersage für Zeichen gemacht wird auf der Basis von vorhandenen Zeichen.

Und zwar wird eine Wahrscheinlichkeitsverteilung zugrunde gelegt, die für jedes Zeichen eines Alphabets auf der Basis seiner relativ hohen Häufigkeit in seinem Korpus eine geschätzte Wahrscheinlichkeit erhält.

Warum arbeiten wir überhaupt mit Wahrscheinlichkeiten? Das ist so eine Frage, die wird seit langer, langer Zeit in der Computerlinguistik diskutiert.

Ist denn die Sprache ein Prozess, der im Wesentlichen als Zufallsprozess zu erklären ist? Nein, das ist nicht so der Fall.

Auf der anderen Seite ist es aber so, dass die Linguisten ja schon immer versucht haben, die Regelhaftigkeiten der Sprachen in Regeln oder in anderen Formulismen zu untersuchen.

Und es zeigt sich aber, dass die Sprache so produktiv ist, dass es immer eine Reihe von Phänomenen gibt, die man dann doch nicht komplett erfassen kann.

Deswegen arbeitet man auch da mit stochastischen Methoden. Man versucht natürlich, das, was regelhaft beschreibbar ist und regelhaft erfassbar ist, mit Regeln auch zu beschreiben.

Aber die anderen Phänomene, die da durchschlüpfen, werden dann normalerweise jedenfalls mit stochastischen Ansätzen versucht, in den Griff zu bekommen.

Und im Ende resultieren dann häufig Methoden, die man auch als hybrid bezeichnet, nämlich sowohl Methoden, die sowohl Regelkomponenten haben, aber eben auch stochastische Komponenten.

Hier geht es um etwas relativ Einfaches, nämlich um die Vorhersage von Zeichen. Und von der Nachrichtentheorie ausgehend spricht man vom Informationsgehalt, der jetzt aber gar nicht etwas Semantisches ist,

sondern Information wird reduziert sozusagen auf die Anordnung von Zeichen in einer Nachricht.

Wenn wir jetzt zwei Sätze haben, die für uns inhaltlich äquivalent sind, aber mit unterschiedlichen Wörtern aufgebaut sind,

dann hätten die nach dieser Beschreibung auch einen ganz unterschiedlichen Informationsgehalt.

Es kommt dazu nicht auf den semantischen Gehalt an, sondern tatsächlich auf die Kodierung in Zeichenfolgen.

Und der Informationsgehalt ist definiert als der Logarithmus von P von S, also der Wahrscheinlichkeit von S, aber negativ.

Und da sagt man also, die Vielfältigkeit, die in einer Nachricht steckt durch die unterschiedlichen Zeichen und ihre Anordnung, ist letztlich das, was in diesem reinen syntaktischen Sinn,

nämlich im Sinne der Anordnung von Zeichen in Zeichenfolgen, den Informationsgehalt bestimmt.

In dem Zusammenhang wird dann auch das Wort Entropie eingeführt.

Die Entropie der Wahrscheinlichkeitsverteilung ist der durchschnittliche Informationsgehalt pro Zeichen über dem gesamten Alphabet.

Und das heißt, man hat damit eben auch so etwas wie eine untere Schranke für jedes Kodierungsverfahren.

Also was ist die mindeste Anzahl von Bits, die ich pro Zeichen brauche?

Wobei natürlich in der Kodierung nicht notwendigerweise für jedes Zeichen des Alphabets die gleiche Anzahl von Bits verbraucht werden muss.

Deswegen ist auch von der untere Schranke die Rede. Man kann Kodierungsverfahren sich überlegen, die für häufig gebrauchte Zeichen eine kurze Kodierung und für weniger häufig gebrauchte Zeichen dafür eine längere Kodierung vorsehen.

Bei der Textkompression unterscheidet man verschiedene Modelle, nämlich zum einen die sogenannten adaptiven Modelle,

die mit jedem gelesenen Zeichen schrittweise eine ursprünglichgebende Wahrscheinlichkeitsverteilung modifizieren, die sich also anpassen.

Dann gibt es diese sogenannte Huffman-Kodierung, der Huffman-Algorithmus, der es in verschiedenen Teilen der Informatik, wo es um Kodierung und Dekodierung geht, sehr weit verbreitet.

Und da ist es eben genau so, dass man kurze Kodierungen dafür für häufige Zeichen und längere für weniger häufige verwendet.

Das ist ein sehr effizientes Verfahren, aber nicht notwendigerweise optimal.

Dann gibt es die sogenannte archämetische Kodierung, wo man einfach Blöcke von Zeichen immer als zu kodierende Symbole ansieht.

Dann zeichenbasierte Modelle, wo man endliche Nachbarschaften betrachtet oder auch endliche Automaten nutzt.